package 算法练习;/**
 * @author： li
 * @date： 2022-01-05 18:07
 * @version 1.0
 */

import java.text.DecimalFormat;
import java.util.Scanner;
import static java.lang.Math.pow;

/**
 问题描述
 　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
 输入格式
 　　一行两个正整数n和m
 输出格式
 　　一个实数P表示答案，保留4位小数。
 样例输入
 2 3
 样例输出
 0.7500
 数据规模和约定
 　　1≤n，m≤20
 */
public class 印章_DP {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        double p = 1.0/n;
        double[][] dp = new double[25][25];
        for ( int i = 1; i <= m; ++i ) {
            for ( int j = 1; j <= n; ++j ) {
                if ( i <  j ) dp[i][j] = 0;
                //j=1，就说明我们买的i张印章里面，只要凑齐1种就行
                //(注意是随便1种就可以了，就比如说abc三种，我们a算1种，b算1种，c算1种，
                // 概率计算的时候就算的是这三种概率的和  没理解的再想想...)
                //
                //其中 j=1 的时候我们也可以分两种情况：一种就是 i=1，这个时候就相当于我们的概率dp[i][j]=1.另一种就是 i>1，
                //我们每个图案的概率都是dp[i][1]= p^i；因为我们的图案不指定哪一种，所以我们的dp[i][j]是n种图案的概率之和，
                //就是p^i*n；因为p=1/n；所以就是p^(i-1)
                if ( j == 1 ) {
                    dp[i][j] = pow (p, i-1);
                }
                //因为我们的凑的印章不规定是哪一种图案，所以我们dp记录我们概率值的时候，
                //就得分情况：要么是有重复的(j已经凑齐了)，要么是没重复的(还有没凑齐的)
                //有重复的：表示前面的 i-1 张里面已经凑齐了 j 种，第 i 张就是重复前面的印章，
                //这个时候前面已经出现过的 j 种印章再出现的时候，它就是 j*p
                //
                //这个时候dp[i][j] = dp[i-1][j] * (j/n) = dp[i-1][j] *(j*p)
                //
                //无重复的：表示前 i-1 张凑齐了 j-1 种，其中，第 i 张就是最后的一种要凑的，
                //因为题目不规定具体求那一种图案的概率，所以我们只需要乘以前面没出现过的印章再出现的概率，
                //因为前面已经出现了 j-1 种了，所以我们剩下没出现的就是 n-(j-1) 种，只要是其中的一种就行了，
                //这个时候凑齐最后一种的概率就是 （n-j+1）*p
                //
                //这个时候dp[i][j] = dp[i-1][j-1]*(n-(j-1))/n = dp[i-1][j-1]*(n-j+1)*p
                //
                //我们只需要把这两种情况相加即可。
                else {
                    dp[i][j] = dp[i-1][j] * (j*1.0/n) + dp[i-1][j-1] * ((n-j+1)*1.0/n);
                }
            }
        }
        for ( int i = 1; i <= m; ++i ) {
            for ( int j = 1; j <= n; ++j ) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
//        DecimalFormat dec = new DecimalFormat("0.0000");
////        String s= dec.format(dp[m][n]);
////        System.out.println(s);
        System.out.printf("%.4f",dp[m][n]);
    }
}
/*
解题思路：

n种图案，m张印章，概率为p=1/n，这个题因为情况不一样，所以我们可以分情况来看。

首先：dp[i][j]就代表i张印章凑齐j种图案的概率

然后我们先来看一般情况：

1) i<j，就说明我们不可能凑齐，这个时候dp[i][j]=0

2) j=1，就说明我们买的i张印章里面，只要凑齐1种就行
(注意是随便1种就可以了，就比如说abc三种，我们a算1种，b算1种，c算1种，概率计算的时候就算的是这三种概率的和  没理解的再想想...)

其中 j=1 的时候我们也可以分两种情况：一种就是 i=1，这个时候就相当于我们的概率dp[i][j]=1.另一种就是 i>1，
我们每个图案的概率都是dp[i][1]= p^i；因为我们的图案不指定哪一种，所以我们的dp[i][j]是n种图案的概率之和，
就是p^i*n；因为p=1/n；所以就是p^(i-1)

接着我们看其它的情况：

3) 因为我们的凑的印章不规定是哪一种图案，所以我们dp记录我们概率值的时候，
就得分情况：要么是有重复的(j已经凑齐了)，要么是没重复的(还有没凑齐的)
有重复的：表示前面的 i-1 张里面已经凑齐了 j 种，第 i 张就是重复前面的印章，
这个时候前面已经出现过的 j 种印章再出现的时候，它就是 j*p

这个时候dp[i][j] = dp[i-1][j] * (j/n) = dp[i-1][j] *(j*p)

无重复的：表示前 i-1 张凑齐了 j-1 种，其中，第 i 张就是最后的一种要凑的，
因为题目不规定具体求那一种图案的概率，所以我们只需要乘以前面没出现过的印章再出现的概率，
因为前面已经出现了 j-1 种了，所以我们剩下没出现的就是 n-(j-1) 种，只要是其中的一种就行了，
这个时候凑齐最后一种的概率就是 （n-j+1）*p

这个时候dp[i][j] = dp[i-1][j-1]*(n-(j-1))/n = dp[i-1][j-1]*(n-j+1)*p

我们只需要把这两种情况相加即可。

最后只需要输出我们要求的dp[m][n] 就可以了。
————————————————
版权声明：本文为CSDN博主「呵呵world」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_58245389/article/details/121877031
* */
